package review.algorithm;

public class InsertionSortByArray {
    static void sort1(int[] arr) {
        for (int i = 1; i < arr.length; i++) { // 默认索引0已排序，从1开始
            if (arr[i - 1] > arr[i]) { // 当未排序元素比已排序max元素小时进入循环
                int j; // 定义一个j 指向已排序max元素 暂时先不定义
                int key = arr[i]; // 定义key变量 保存 arr[i]的值
                // j为已排序max元素 循环条件为j>=0 保证不越界 且 j索引的值大于key 然后每次循环j--递减
                for (j = i - 1; j >= 0 && arr[j] > key; j--) {
                    arr[j + 1] = arr[j]; // j代表的元素向后空一格
                }
                arr[j + 1] = key; // 将之前保存的key存放在空出的 arr[j-1]
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {70, 30, 40, 10, 80, 20, 90, 100, 75, 60, 45};
        sort1(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
